package com.zlk.algorithm.algorithm.dynamicPlan.PartitionedKnapsack074;

import org.junit.Test;

// 正则表达式匹配
// 给你字符串s、字符串p
// s中一定不含有'.'、'*'字符，p中可能含有'.'、'*'字符
// '.' 表示可以变成任意字符，数量1个
// '*' 表示可以让 '*' 前面那个字符数量任意(甚至可以是0个)
// p中即便有'*'，一定不会出现以'*'开头的情况，也一定不会出现多个'*'相邻的情况(无意义)
// 请实现一个支持 '.' 和 '*' 的正则表达式匹配
// 返回p的整个字符串能不能匹配出s的整个字符串
// 测试链接 : https://leetcode.cn/problems/regular-expression-matching/
public class Code04_RegularExpressionMatching {
    @Test
    public void test(){
        System.out.println(isMatch("aa", "a"));
    }

    public boolean isMatch(String s, String p) {

        //return f(s.toCharArray(),p.toCharArray(),0,0);
        return f2(s.toCharArray(),p.toCharArray());
    }

    //
    private boolean f2(char[] s, char[] p) {
        boolean[][] dp = new boolean[s.length+1][p.length+1];
        dp[s.length][p.length] = true;
        //j走完了，i没走完 false 只用设置true就行默认为false
//     i==s.length   if(j+1<p.length&&p[j+1]=='*'){
//            return f(s,p,i,j+2);
        for (int j = p.length-1; j>=0; j--) {
            dp[s.length][j] = (j+1<p.length&&p[j+1]=='*')||dp[s.length][j+2];
        }
        for (int i = s.length-1; i >=0 ; i--) {
            for (int j = p.length-1; j >=0 ; j--) {
                if(j+1<p.length&&p[j+1]=='*') {//j+1 等于*
                    dp[i][j] = ((s[i] == p[j] || p[j] == '.') && dp[i + 1][j])||dp[i][j+2];
                }else{
                    dp[i][j] = (s[i] == p[j] || p[j] == '.') &&dp[i+1][j+1];
                }
            }
        }
        return dp[0][0];
    }

    /**
     * 递归含义，s,p串分别从i，j位置出发成功匹配
     *
     * base case
     * 1、i==s.len && j==p.len
     *    return true
     * @param s
     * @param p
     * @param i
     * @param j
     * @return
     */
    private boolean f(char[] s, char[] p, int i, int j) {
        //base case
        if(i==s.length){
            if(j==p.length){
                return true;
            }else{
                //j没走完
                // '*' 表示可以让 '*' 前面那个字符数量任意(甚至可以是0个)
                // 所以j+1等于* 才可能存在true的情况，
                if(j+1<p.length&&p[j+1]=='*'){
                    return f(s,p,i,j+2);
                }else{
                    return false;
                }
            }
        }else{
            //j走完了，i没走完
            if(j==p.length){
                return false;
            }
        }
        // '*' 表示可以让 '*' 前面那个字符数量任意(甚至可以是0个)
        //判断j+1 是不是 *
        if(j+1<p.length&&p[j+1]=='*'){//j+1 等于*
            if(s[i] == p[j] || p[j] == '.'){
                //可以不要，可以要
                boolean b1 = f(s,p,i,j+2);
                boolean b2 = f(s,p,i+1,j);
                return b1||b2;
            }else{//不等于只能不要
                return f(s,p,i,j+2);
            }
        }else{//j+1 不等于 *
            //'.' 表示可以变成任意字符，数量1个
//            if(sv==pv||pv=='.'){
//                return f(s,p,i+1,j+1);
//            }else{
//                return false;
//            }
            //优化上述代码
            return (s[i] == p[j] || p[j] == '.') && f(s, p, i + 1, j + 1);
        }
    }


}
